package question0045_jump_game_ii;

/**
 * https://leetcode-cn.com/problems/jump-game-ii/
 *
 * 贪心算法。
 *
 * 假设我们现在在索引i的位置。
 *
 * 如果索引i的值为0，那么我们不可能再继续前进了，这种情况舍弃。
 *
 * 如果索引i的值不为0，那么我们下一步可以走到索引i + k(1 <= k <= nums[i])。
 * 而在索引i + k我们又可以走到索引i + k + p(1 <= p <= nums[i + k])，我们选取索引i + k的原则是i + k + p取得最大值。
 *
 * 对于贪心算法而言，其实现永远不是重点，其重点在于为什么可以使用贪心算法。那么，为什么本题可以这样使用贪心算法呢？
 *
 * （1）如果此时i + k + p的最大值仍然小于（数组的长度 - 1），说明经过此步还未能抵达数组中最后一个元素。
 *
 * 对于索引i而言，假设索引i下一步的最优解为索引i + k。索引i + k的下一步所能到达的范围是索引i + k + 1 ~ i + k + nums[i + k]。
 *
 * 假设索引i + k不是索引i下一步的最优解，索引i下一步的最优解为索引i + j(j != k)。
 * 索引i + j的下一步所能到达的范围是索引i + j + 1 ~ i + j + nums[i + j]，
 * 由索引i + k的定义可知，i + j + nums[i + j] <= i + k + nums[i + k]。
 *
 * 如果j >= k，那么i + j + 1 >= i + k + 1，索引i + j的下一步所能到达的范围是小于索引i + k所能到达的范围的，
 * 即如果索引i + j能到的地方，索引i + k也能到，但是索引i + k能到的地方，索引i + j却不一定能到。因此索引i下一步的最优解一定只可能是i + k。
 *
 * 如果j < k，对于索引i + k + 1及其之后的索引位置，索引i + j的下一步所能到达的范围是小于索引i + k所能到达的范围的，
 * 即如果索引i + j能到的地方，索引i + k也能到，但是索引i + k能到的地方，索引i + j却不一定能到。
 * 而对于索引i + k + 1之前的索引位置，索引i + k是到不了的，索引i + j能到，但是此时多走了一步路。
 * 因为我们最终肯定是要跨过索引i + k，我们本可以一步到达索引i + k的位置，下一步就跨过索引i + k了，
 * 现在我们第一步到达索引i + j的位置，下一步还不能保证跨过索引i + k。因此索引i下一步的最优解一定只可能是i + k。
 *
 * （2）如果此时i + k + p的最大值大于等于（数组的长度 - 1），说明经过此步能抵达数组中最后一个元素，显然索引i + k是最优解。
 *
 * 时间复杂度是O(n)，其中n为nums数组的长度。空间复杂度是O(1)。
 *
 * 执行用时：4ms，击败78.42%。消耗内存：42MB，击败68.36%。
 */
public class Solution {
    public int jump(int[] nums) {
        int n = nums.length, steps = 0, i = 0;
        while (i < n - 1) {
            steps++;
            if (i + nums[i] >= n - 1) {
                return steps;
            }
            int k = i + 1;
            for (int j = i + 1; j <= i + nums[i]; j++) {
                if (j + nums[j] > k + nums[k]) {    //选取k的原则是i + k + nums[k]达到最大
                    k = j;
                }
            }
            i = k;  //下一步是索引k
        }
        return steps;
    }
}